{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Determine the Minimum Sum of a k-avoiding Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #k-avoiding 数组的最小总和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数 <code>n</code> 和 <code>k</code> 。</p>\n",
    "\n",
    "<p>对于一个由 <strong>不同</strong> 正整数组成的数组，如果其中不存在任何求和等于 k 的不同元素对，则称其为 <strong>k-avoiding</strong> 数组。</p>\n",
    "\n",
    "<p>返回长度为 <code>n</code> 的 <strong>k-avoiding</strong> 数组的可能的最小总和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, k = 4\n",
    "<strong>输出：</strong>18\n",
    "<strong>解释：</strong>设若 k-avoiding 数组为 [1,2,4,5,6] ，其元素总和为 18 。\n",
    "可以证明不存在总和小于 18 的 k-avoiding 数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, k = 6\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>可以构造数组 [1,2] ，其元素总和为 3 。\n",
    "可以证明不存在总和小于 3 的 k-avoiding 数组。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n, k &lt;= 50</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [determine-the-minimum-sum-of-a-k-avoiding-array](https://leetcode.cn/problems/determine-the-minimum-sum-of-a-k-avoiding-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [determine-the-minimum-sum-of-a-k-avoiding-array](https://leetcode.cn/problems/determine-the-minimum-sum-of-a-k-avoiding-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n4', '2\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        if n<=k//2:\n",
    "            return n*(n+1)//2\n",
    "        t=k//2\n",
    "        return (t+1)*t//2+(n-t)*(k+k+n-t-1)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        if k<3 or n<k//2+1:\n",
    "            return n*(n+1)//2\n",
    "        return (1+k//2)*(k//2)//2+(k+k+n-k//2-1)*(n-k//2)//2;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        ans=0\n",
    "        # a=[]\n",
    "        bef=0\n",
    "        cur=1\n",
    "        for i in range(n):\n",
    "            if cur<k:\n",
    "                for j in range(cur):\n",
    "                    if cur+j>k:\n",
    "                        break\n",
    "                    elif cur+j==k:\n",
    "                        cur=k\n",
    "                        break\n",
    "            ans+=cur\n",
    "            # a.append(cur)\n",
    "            bef=cur\n",
    "            cur+=1\n",
    "        # print(a)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        data = {}\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        c = 1\n",
    "        while i < n:\n",
    "            if data.get(c):\n",
    "                c += 1\n",
    "                continue\n",
    "            else:\n",
    "                ans += c\n",
    "                data[k - c] = 1\n",
    "                c += 1\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        m = min(k // 2, n)\n",
    "        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        s = (1 + n) * n // 2\n",
    "        e = k // 2 - 1\n",
    "        if 1 == k % 2:\n",
    "            e += 1\n",
    "        t = max(n + 1, k)\n",
    "        for i in range(e, 0, -1):\n",
    "            d = k - i\n",
    "            if d <= n:\n",
    "                s = s + (t - d)\n",
    "                t += 1\n",
    "            else:\n",
    "                break\n",
    "        return s "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        m = min(k // 2, n)\n",
    "        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        if k in (1,2): return sum(list(range(1,n+1)))\n",
    "        half_k = k//2\n",
    "        tmp = list(range(1, half_k+1))\n",
    "        if n <= k//2:\n",
    "            return sum(tmp[:n])\n",
    "        else:\n",
    "            return sum(tmp) + sum(list(range(k,k+(n-half_k))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        arr = []\n",
    "        m = {}\n",
    "        res = 0\n",
    "        for i in range(1,111):\n",
    "            if len(arr) == n:\n",
    "                break\n",
    "            if i in m:\n",
    "                continue\n",
    "            m[i] = 1\n",
    "            m[k - i] = 1\n",
    "            arr.append(i)\n",
    "            res = res + i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        m = k//2\n",
    "        return sum(i for i in range(min(m, n)+1)) + sum(i for i in range(k, k+n-m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        s=[]\n",
    "        sum=0\n",
    "        i=1\n",
    "        while len(s)<n :\n",
    "            if s.count(k-i)==0:\n",
    "                s.append(i)\n",
    "                \n",
    "                sum+=i\n",
    "            i+=1\n",
    "        return sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        f=min(k//2,n)\n",
    "        return (1+f)*f//2+(2*k+n-f-1)*(n-f)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        j=1\n",
    "        total=0\n",
    "        used=set()\n",
    "        for i in range(n):\n",
    "            while k-j in used:\n",
    "                j+=1\n",
    "            total+=j\n",
    "            used.add(j)\n",
    "            j+=1\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        m=k//2\n",
    "        if n<=m:\n",
    "            return (1+n)*n>>1\n",
    "        else:\n",
    "            n-=m\n",
    "            return ((1+m)*m+(k+k+n-1)*n)>>1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        cant = set()\n",
    "        total = 0\n",
    "        for i in range(1, 25000):\n",
    "            if k - i not in cant:\n",
    "                total += i \n",
    "                cant.add(i)\n",
    "                if len(cant) == n:\n",
    "                    return total\n",
    "        print(i)\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        s=0\n",
    "        i=1\n",
    "        flag=0\n",
    "        for _ in range(n):\n",
    "            if i>k/2.0 and flag==0:\n",
    "                i=k\n",
    "                flag=1\n",
    "            #print(i)\n",
    "            s+=i\n",
    "            i+=1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        ans = 0\n",
    "        i = 1\n",
    "        while n:\n",
    "            if i <= k // 2:\n",
    "                ans += i\n",
    "                i += 1\n",
    "                n -= 1\n",
    "                continue\n",
    "            if i < k:\n",
    "                i = k\n",
    "                continue\n",
    "            ans += i\n",
    "            i += 1\n",
    "            n -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        \"\"\"\n",
    "        对于[1, k-1]内的数字\n",
    "        1和k-1只能选一个\n",
    "        2和k-2只能选一个\n",
    "        3和k-3只能选一个\n",
    "        ...\n",
    "        一直到k/2(向下取整),无论k是奇数还是偶数都可以选\n",
    "        设m=min(k/2, n),分为两段m 和 n-m\n",
    "        \"\"\"\n",
    "        m = min(k // 2, n)\n",
    "        return ((m + 1) * m + (2 * k + n - m - 1) * (n - m)) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        pairs = set()\n",
    "        for i in range(1, (k-1)//2+1):\n",
    "            pairs.add(k-i)\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        for i in range(1,2*n+1):\n",
    "            if i in pairs: continue\n",
    "            else:\n",
    "                cnt+= 1\n",
    "                ans += i\n",
    "            if cnt == n: break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        num = a = 0\n",
    "        i =1\n",
    "        while a!=n:\n",
    "            if i > (k/2) and i < k:\n",
    "                i += 1\n",
    "                continue\n",
    "            else:\n",
    "                num += i\n",
    "                i += 1\n",
    "                a += 1\n",
    "            \n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        \n",
    "        st = set()\n",
    "        for i in range(1,10000):\n",
    "            t = k-i\n",
    "            if t in st:continue\n",
    "            else:\n",
    "                st.add(i)\n",
    "            if len(st)>=n:break\n",
    "        \n",
    "        return sum(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        ans=0\n",
    "        if n<=k//2:\n",
    "            return (1+n)*n//2\n",
    "        p=k//2\n",
    "        q=n-p\n",
    "        ans+=p*(p+1)//2\n",
    "        ans+=(2*k+q-1)*q//2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        m = min(k // 2, n)\n",
    "        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        m = min(k // 2, n)\n",
    "        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        m = k // 2\n",
    "        \n",
    "        if n <= m:\n",
    "            return (1 + n) * n // 2\n",
    "        else:\n",
    "            return (1 + m) * m // 2 + (k + k + n - m - 1) * (n - m) // 2\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        m = min(k // 2, n)\n",
    "        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        \n",
    "        \n",
    "        myset = set()\n",
    "        i,num = 0,1\n",
    "        while(i<n):\n",
    "            if num>=k or k-num not in myset:\n",
    "                myset.add(num)\n",
    "                num += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                num += 1\n",
    "        return sum(myset)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        m = min(k // 2, n)\n",
    "        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        s = set()\n",
    "        res = 0\n",
    "        for i in range(1, 10000):\n",
    "            if k - i not in s:\n",
    "                s.add(i)\n",
    "                res += i \n",
    "            if len(s) == n:\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        m = min(k // 2, n)\n",
    "        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        arr = []\n",
    "        count = k/2\n",
    "        for i in range(1,100):\n",
    "            if i >count and i < k:\n",
    "                continue\n",
    "            else:\n",
    "                arr.append(i)\n",
    "                if len(arr)==n:\n",
    "                    break\n",
    "        return sum(arr)\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        b = k//2\n",
    "        if n<=b:\n",
    "            return (1+n)*n//2\n",
    "        else:\n",
    "            c, d = k, k+(n-b)\n",
    "            return (1+b)*b//2 + (c+d-1)*(d-c)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        s=0\n",
    "        if k%2==0:\n",
    "            if n>=(k//2)+1:\n",
    "                for i in range((k//2)+1):\n",
    "                    s+=i\n",
    "                for j in range(k,n+(k//2)):\n",
    "                    s+=j\n",
    "            else:\n",
    "                for k in range(n+1):\n",
    "                    s+=k\n",
    "        else:\n",
    "            if n>=(k+1)//2:\n",
    "                for p in range(((k-1)//2)+1):\n",
    "                    s+=p\n",
    "                for q in range(k,n+(k+1)//2):\n",
    "                    s+=q\n",
    "            else:\n",
    "                for u in range(n+1):\n",
    "                    s+=u\n",
    "        return s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        l1 =[]\n",
    "        m = k//2\n",
    "        for i in range(1,m+1):\n",
    "            l1.append(i)\n",
    "            if len(l1) == n :\n",
    "                break\n",
    "        else :\n",
    "            num = 0\n",
    "            while 1 :\n",
    "                l1.append(k+num)\n",
    "                if len(l1) == n :\n",
    "                    break\n",
    "                num += 1\n",
    "        s = 0\n",
    "        for j in l1 :\n",
    "            s += j\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        sumlist=set()\n",
    "        for i in range(1,k):\n",
    "            if len(sumlist)>=n:\n",
    "                return sum(sumlist)\n",
    "            if k-i in sumlist:\n",
    "                continue\n",
    "            else:\n",
    "                sumlist.add(i)\n",
    "        return sum(sumlist)+sum([i for i in range(k,k+n-len(sumlist))])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        arr = [i for i in range(1 , n + 1)]\n",
    "        flg = True\n",
    "        mx = n + 1\n",
    "        while flg:\n",
    "            # we check if there are still pairs for us to alter\n",
    "            # a a a b b b\n",
    "            #print(arr)\n",
    "            flg = False\n",
    "            for i in range(len(arr)):\n",
    "                val = arr[i]\n",
    "                nxt = bisect_left(arr , k - val)\n",
    "                if nxt < len(arr) and arr[nxt] + val == k and i != nxt:\n",
    "                    #print(i , nxt , arr)\n",
    "                    flg = True\n",
    "                    arr = arr[:nxt] + arr[nxt + 1:] + [mx]\n",
    "                    mx += 1\n",
    "                    break\n",
    "                    #alter the array by moving the relatively larger element to the right of the current array\n",
    "        return sum(arr)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        m = min(k//2, n)\n",
    "        return ((m+1)*m + (2*k + n - m - 1)*(n-m)) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        m = k//2\n",
    "        return n * (n+1) // 2 if n <= m else m * (m+1) // 2 + (k + k + n - m - 1) * (n - m) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        # num = 0\n",
    "        # a = 0\n",
    "        # count = k/2\n",
    "        # i =1\n",
    "        # while a!=n:\n",
    "        #     if i > count and i < k:\n",
    "        #         i += 1\n",
    "        #         continue\n",
    "        #     else:\n",
    "        #         num += i\n",
    "        #         a += 1\n",
    "        #         i += 1\n",
    "            \n",
    "        # return num\n",
    "        m = min(k // 2, n)\n",
    "        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) // 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "\n",
    "        s =set() \n",
    "        sum = 0 \n",
    "        i, cnt= 1,0\n",
    "        while cnt < n:\n",
    "            if i not in s:\n",
    "                sum += i \n",
    "                s.add(k-i)\n",
    "                cnt+=1\n",
    "            i+=1\n",
    "        return sum \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        pre_cnt = min(n, k // 2)\n",
    "        ans = (pre_cnt + 1) * pre_cnt // 2\n",
    "    \n",
    "        last_cnt = n - pre_cnt\n",
    "        if last_cnt > 0:\n",
    "            ans += (k + k + last_cnt - 1) * last_cnt // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        # 和前面一题一样，数值范围是简化版\n",
    "        target = k\n",
    "        if n <= target//2:\n",
    "            ans = (1 + n) * n // 2\n",
    "        else:\n",
    "            ans = (1 + target//2) * (target//2) // 2\n",
    "        if n > target//2:\n",
    "            n -= target//2 # 看还剩下多少数字\n",
    "            ans += (target + target + n - 1) * n // 2\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        m = min(k // 2, n)\n",
    "        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        m=k//2\n",
    "        res=n*(n+1)//2\n",
    "        if n>m:\n",
    "            res+=(k-1-m)*(n-m)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        ban_set = set()\n",
    "        result = 0\n",
    "        cnt = 0\n",
    "        num = 1\n",
    "        while(cnt < n):\n",
    "            if(num in ban_set):\n",
    "                num += 1\n",
    "                continue\n",
    "            else:\n",
    "                result += num \n",
    "                ban_set.add(k - num)\n",
    "                cnt += 1\n",
    "                num += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        ban_set = set()\n",
    "        result = 0\n",
    "        cnt = 0\n",
    "        num = 1\n",
    "        while(cnt < n):\n",
    "            if(num in ban_set):\n",
    "                num += 1\n",
    "                continue\n",
    "            else:\n",
    "                result += num \n",
    "                ban_set.add(k - num)\n",
    "                cnt += 1\n",
    "                num += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        arr = []\n",
    "        count = k/2\n",
    "        i =1\n",
    "        while len(arr)!=n:\n",
    "            if i > count and i < k:\n",
    "                i += 1\n",
    "                continue\n",
    "            else:\n",
    "                arr.append(i)\n",
    "                i +=1\n",
    "            \n",
    "        return sum(arr)\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        x = min(n, k // 2)\n",
    "        return x * (x+1) + (n-x) * (k*2+n-x-1) >> 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        def get(a, b):\n",
    "            return (a + b) * (b - a + 1) // 2\n",
    "        \n",
    "        if k == 1:\n",
    "            return get(1, n)\n",
    "        \n",
    "        if n > k//2:\n",
    "            return get(1, k // 2) + get(k, k + n - (k // 2) - 1 )\n",
    "        else:\n",
    "            return get(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        avoid_set = set()\n",
    "        ans, count = 0, 0\n",
    "        for i in range(1, n + k + 1):\n",
    "            if i <= k and i in avoid_set:\n",
    "                continue\n",
    "            ans += i\n",
    "            count += 1\n",
    "            avoid_set.add(k - i)\n",
    "            if count == n:\n",
    "                return ans\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        num = 0\n",
    "        a = 0\n",
    "        count = k/2\n",
    "        i =1\n",
    "        while a!=n:\n",
    "            if i > count and i < k:\n",
    "                i += 1\n",
    "                continue\n",
    "            else:\n",
    "                num += i\n",
    "                i += 1\n",
    "                a += 1\n",
    "            \n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        s = [i + 1 for i in range(n)]\n",
    "        for i in range(1, n):\n",
    "            if s[i] + s[i - 1] >= k and s[i] < k:\n",
    "                while i < n:\n",
    "                    s[i] = k\n",
    "                    k += 1\n",
    "                    i += 1\n",
    "                break\n",
    "        return sum(s)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        m = min(k // 2, n)\n",
    "        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        ans = []\n",
    "        left = 1\n",
    "        temp= set()\n",
    "        while len(ans) < n:\n",
    "            for per in ans:\n",
    "                if per + left == k:\n",
    "                    break\n",
    "            else:\n",
    "                ans.append(left)\n",
    "            left += 1\n",
    "        return sum(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        #这道题根本没有难在编程上，而是难在了思考上\n",
    "        #用不完整的思路还不如不写\n",
    "        #这道题的本质是求两个等差数列\n",
    "        n1 = k//2\n",
    "\n",
    "        if n1 >= n:\n",
    "            return (1+n)*n//2\n",
    "        if n1 < n:\n",
    "            return (1+n1)*n1//2 + (k+k+n-n1-1)*(n-n1)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        s = set()\n",
    "        res = 0\n",
    "        for i in range(1, 100000):\n",
    "            if k - i not in s:\n",
    "                s.add(i)\n",
    "                res += i \n",
    "            if len(s) == n:\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        i,c=1,0\n",
    "        s=set()\n",
    "        #s.add(k)\n",
    "        ans=0\n",
    "        while c<n:\n",
    "            if i<=k :\n",
    "                if i not in s:\n",
    "         #           print(i)\n",
    "                    c+=1\n",
    "                    s.add(k-i)\n",
    "                    ans+=i\n",
    "                    i+=1\n",
    "                else:\n",
    "                    i+=1\n",
    "            else :\n",
    "                ans+=i\n",
    "                c+=1\n",
    "                i+=1  \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        m = min(k // 2, n)\n",
    "        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        #这道题根本没有难在编程上，而是难在了思考上\n",
    "        #用不完整的思路还不如不写\n",
    "        n1 = k//2\n",
    "\n",
    "        if n1 >= n:\n",
    "            return (1+n)*n//2\n",
    "        if n1 < n:\n",
    "            return (1+n1)*n1//2 + (k+k+n-n1-1)*(n-n1)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        m = min(k // 2, n)\n",
    "        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        d = set()\n",
    "        ret = 0\n",
    "        i, t = 1, 0\n",
    "        while t < n:\n",
    "            if i < k and k-i in d:\n",
    "                pass\n",
    "            else:\n",
    "                ret += i\n",
    "                t += 1\n",
    "                d.add(i)\n",
    "            i += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        # ans = []\n",
    "        # left = 1\n",
    "        # temp= set()\n",
    "        # while len(ans) < n:\n",
    "        #     for per in ans:\n",
    "        #         if per + left == k:\n",
    "        #             break\n",
    "        #     else:\n",
    "        #         ans.append(left)\n",
    "        #     left += 1\n",
    "        # return sum(ans)\n",
    "\n",
    "        count = 0\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while count <= n:\n",
    "            if k // 2 < i < k:\n",
    "                pass\n",
    "            else:\n",
    "                ans += i\n",
    "                count += 1\n",
    "            i += 1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        arr = []\n",
    "        \n",
    "        count = k/2\n",
    "        for i in range(1,100):\n",
    "            if i >count and i < k:\n",
    "                continue\n",
    "            else:\n",
    "                arr.append(i)\n",
    "                if len(arr)==n:\n",
    "                    break\n",
    "        print(arr)\n",
    "        return sum(arr)\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        max_ = k // 2\n",
    "        cnt = 0\n",
    "        sum_ = 0\n",
    "        for i in range(1, max_ + 1):\n",
    "            sum_ += i\n",
    "            cnt += 1\n",
    "            if cnt == n:\n",
    "                return sum_\n",
    "        \n",
    "        for j in range(k, n + max_ + 2):\n",
    "            sum_ += j\n",
    "            cnt += 1\n",
    "            if cnt == n:\n",
    "                return sum_\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        arr = []\n",
    "        \n",
    "        cur = 1\n",
    "        st = set()\n",
    "        \n",
    "        while len(arr) < n:\n",
    "            x = k - cur\n",
    "            if x not in st:\n",
    "                arr.append(cur)\n",
    "                st.add(cur)\n",
    "            cur += 1\n",
    "        \n",
    "        return sum(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        if n <= k//2:\n",
    "            return (n+1)*n//2\n",
    "        else:\n",
    "            return (k//2+1) * (k//2) //2 + (n - (k//2)) * (2 * k + n - (k//2) - 1) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        result = list(range(1,n+1))\n",
    "        left = 0\n",
    "        right = n-1\n",
    "        while left < right:\n",
    "            if result[left] + result[right] < k:\n",
    "                left += 1\n",
    "            elif result[left] + result[right] > k:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        for i in range(right+1, n):\n",
    "            result[i] += left\n",
    "        return sum(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        if k == 1: return sum(range(1, n + 1))\n",
    "        \n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = []\n",
    "\n",
    "        dp[1] = [1]\n",
    "        \n",
    "        for i in range(2, n + 1):\n",
    "            if dp[i - 1][-1] >= k:\n",
    "                tail = dp[i - 1][-1]\n",
    "                dp[i] = dp[i - 1] + [tail + 1]\n",
    "            else:\n",
    "                head = dp[i - 1][0]\n",
    "                tail = dp[i - 1][-1]\n",
    "                \n",
    "                range_left = k - tail\n",
    "                range_right = k - head\n",
    "                \n",
    "                if tail + 1 < range_left:\n",
    "                    dp[i] = dp[i - 1] + [tail + 1]\n",
    "                else:\n",
    "                    dp[i] = dp[i - 1] + [range_right + 1]\n",
    "        return sum(dp[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self, x, a, k):\n",
    "        c = a + [x]\n",
    "        n = len(c)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if c[i] + c[j] == k:\n",
    "                    return False\n",
    "        return True\n",
    "        \n",
    "        \n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        a = []\n",
    "        for i in range(1, 200):\n",
    "            if len(a) == n:\n",
    "                res = 0\n",
    "                print(a)\n",
    "                for v in a: \n",
    "                    res += v\n",
    "                return res\n",
    "            if self.check(i, a, k) == True:\n",
    "                a.append(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        ret = 0;\n",
    "        for i in range(1, min(k//2, n)+1):\n",
    "            ret += i;\n",
    "            n-=1;\n",
    "        print(ret, n)\n",
    "        for i in range(k, k+n):\n",
    "            ret += i;\n",
    "        return ret; \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSum(self, n: int, k: int) -> int:\n",
    "        if n <= k // 2:\n",
    "            return n * (n + 1) // 2\n",
    "        else:\n",
    "            m = k // 2\n",
    "            return m * (m + 1) // 2 + (n - m) * (k + k + n - m - 1) // 2 "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
